package algorithm.problems.tree;

/**
 * Created by gouthamvidyapradhan on 03/10/2017.
 * <p>
 * Follow up for problem "Populating Next Right Pointers in Each Node".
 * <p>
 * What if the given tree could be any binary tree? Would your previous solution still work?
 * <p>
 * Note:
 * <p>
 * You may only use constant extra space.
 * For example,
 * Given the following binary tree,
 * 1
 * /  \
 * 2    3
 * / \    \
 * 4   5    7
 * After calling your function, the tree should look like:
 * 1 -> NULL
 * /  \
 * 2 -> 3 -> NULL
 * / \    \
 * 4-> 5 -> 7 -> NULL
 */
public class NextRightPointerII {

    public static void main(String[] args) throws Exception {
        TreeLinkNode root = new TreeLinkNode(1);
        root.left = new TreeLinkNode(2);
        root.right = new TreeLinkNode(3);
        root.right.right = new TreeLinkNode(4);
        root.right.right.left = new TreeLinkNode(5);
        root.right.right.right = new TreeLinkNode(6);
        new NextRightPointerII().connect(root);
    }

    public void connect(TreeLinkNode root) {
        TreeLinkNode prev = new TreeLinkNode(0);
        TreeLinkNode first = null;
        while (root != null) {
            if (root.left != null) {
                prev.next = root.left;
                prev = root.left;
                if (first == null) {
                    first = root.left;
                }
            }
            if (root.right != null) {
                prev.next = root.right;
                prev = root.right;
                if (first == null) {
                    first = root.right;
                }
            }
            root = root.next;
            if (root == null) {
                root = first;
                first = null;
                prev = new TreeLinkNode(0);
            }
        }
    }

    public static class TreeLinkNode {
        int val;
        TreeLinkNode left, right, next;

        TreeLinkNode(int x) {
            val = x;
        }
    }
}
